{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Guess Number Higher or Lower II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming #game-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划 #博弈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMoneyAmount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #猜数字大小 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们正在玩一个猜数游戏，游戏规则如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>我从&nbsp;<code>1</code><strong>&nbsp;</strong>到 <code>n</code> 之间选择一个数字。</li>\n",
    "\t<li>你来猜我选了哪个数字。</li>\n",
    "\t<li>如果你猜到正确的数字，就会 <strong>赢得游戏</strong> 。</li>\n",
    "\t<li>如果你猜错了，那么我会告诉你，我选的数字比你的 <strong>更大或者更小</strong> ，并且你需要继续猜数。</li>\n",
    "\t<li>每当你猜了数字 <code>x</code> 并且猜错了的时候，你需要支付金额为 <code>x</code> 的现金。如果你花光了钱，就会<strong> 输掉游戏</strong> 。</li>\n",
    "</ol>\n",
    "\n",
    "<p>给你一个特定的数字 <code>n</code> ，返回能够 <strong>确保你获胜</strong> 的最小现金数，<strong>不管我选择那个数字</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/10/graph.png\" style=\"width: 505px; height: 388px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 10\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>制胜策略如下：\n",
    "- 数字范围是 [1,10] 。你先猜测数字为 7 。\n",
    "&nbsp;   - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $7 。\n",
    "&nbsp;   - 如果我的数字更大，则下一步需要猜测的数字范围是 [8,10] 。你可以猜测数字为 9 。\n",
    "&nbsp;       - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $9 。\n",
    "&nbsp;       - 如果我的数字更大，那么这个数字一定是 10 。你猜测数字为 10 并赢得游戏，总费用为 $7 + $9 = $16 。\n",
    "&nbsp;       - 如果我的数字更小，那么这个数字一定是 8 。你猜测数字为 8 并赢得游戏，总费用为 $7 + $9 = $16 。\n",
    "&nbsp;   - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,6] 。你可以猜测数字为 3 。\n",
    "&nbsp;       - 如果这是我选中的数字，你的总费用为 $7 。否则，你需要支付 $3 。\n",
    "&nbsp;       - 如果我的数字更大，则下一步需要猜测的数字范围是 [4,6] 。你可以猜测数字为 5 。\n",
    "&nbsp;           - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $5 。\n",
    "&nbsp;           - 如果我的数字更大，那么这个数字一定是 6 。你猜测数字为 6 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。\n",
    "&nbsp;           - 如果我的数字更小，那么这个数字一定是 4 。你猜测数字为 4 并赢得游戏，总费用为 $7 + $3 + $5 = $15 。\n",
    "&nbsp;       - 如果我的数字更小，则下一步需要猜测的数字范围是 [1,2] 。你可以猜测数字为 1 。\n",
    "&nbsp;           - 如果这是我选中的数字，你的总费用为 $7 + $3 = $10 。否则，你需要支付 $1 。\n",
    "&nbsp;           - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $7 + $3 + $1 = $11 。\n",
    "在最糟糕的情况下，你需要支付 $16 。因此，你只需要 $16 就可以确保自己赢得游戏。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>只有一个可能的数字，所以你可以直接猜 1 并赢得游戏，无需支付任何费用。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 2\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>有两个可能的数字 1 和 2 。\n",
    "- 你可以先猜 1 。\n",
    "&nbsp;   - 如果这是我选中的数字，你的总费用为 $0 。否则，你需要支付 $1 。\n",
    "&nbsp;   - 如果我的数字更大，那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏，总费用为 $1 。\n",
    "最糟糕的情况下，你需要支付 $1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 200</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [guess-number-higher-or-lower-ii](https://leetcode.cn/problems/guess-number-higher-or-lower-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [guess-number-higher-or-lower-ii](https://leetcode.cn/problems/guess-number-higher-or-lower-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10', '1', '2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dict1 = {2: 1, 3: 2, 4: 4, 5: 6, 6: 8, 7: 10, 8: 12, 9: 14, 10: 16, 16: 34, 18: 42,\n",
    "                 25: 64, 45: 144, 56: 198, 63: 226, 77: 282, 83: 310, 94: 365, 109: 454, 115: 494,\n",
    "                 120: 529, 139: 630, 141: 640, 151: 698, 160: 743, 176: 823, 183: 858, 191: 898,\n",
    "                 200: 952}\n",
    "        result = dict1.get(n)\n",
    "        if result is not None:\n",
    "            return result\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        if(n < 4):return n -1\n",
    "        result = [[0] * n for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            result[i-1][i] = i\n",
    "        for i in range(2,n):\n",
    "            result[i-2][i] = i\n",
    "        for len in range(3,n):\n",
    "            pos = 0\n",
    "            while(pos + len <n):\n",
    "                temp = 9999999\n",
    "                for i in range(pos+1,pos+len):\n",
    "                    temp = min(temp,  i+1 +max(result[i+1][pos+len],result[pos][i-1]))\n",
    "                result[pos][pos+len] = temp\n",
    "                pos += 1\n",
    "        return result[0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        liebiao=[0, 1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24, 27, 30, 34, 38, 42, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 86, 90, 94, 98, 102, 106, 110, 114, 119, 124, 129, 134, 139, 144, 149, 154, 160, 166, 172, 178, 182, 186, 190, 194, 198, 202, 206, 210, 214, 218, 222, 226, 230, 234, 238, 242, 246, 250, 254, 258, 262, 266, 270, 274, 278, 282, 286, 290, 295, 300, 305, 310, 315, 320, 325, 330, 335, 340, 345, 350, 355, 360, 365, 370, 376, 382, 388, 394, 400, 406, 412, 418, 424, 430, 436, 442, 448, 454, 460, 466, 473, 480, 487, 494, 501, 508, 515, 522, 529, 536, 543, 550, 555, 560, 565, 570, 575, 580, 585, 590, 595, 600, 605, 610, 615, 620, 625, 630, 635, 640, 645, 650, 655, 660, 666, 674, 680, 686, 692, 698, 703, 708, 713, 718, 723, 728, 733, 738, 743, 748, 753, 758, 763, 768, 773, 778, 783, 788, 793, 798, 803, 808, 813, 818, 823, 828, 833, 838, 843, 848, 853, 858, 863, 868, 873, 878, 883, 888, 893, 898, 904, 910, 916, 922, 928, 934, 940, 946, 952 ]\n",
    "        return liebiao[n-1]\n",
    "        f = [[0] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                f[i][j] = j + f[i][j - 1]\n",
    "                for k in range (i, j):\n",
    "                    f[i][j] = min(f[i][j], k + max(f[i][k - 1], f[k + 1][j]))\n",
    "        return f[1][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# n = 200\n",
    "# ans = [[-1 for j in range(n+1)] for i in range(n+1)]\n",
    "# def search(x,y):\n",
    "#     if y < x:\n",
    "#         return 0\n",
    "#     if y == x:\n",
    "#         ans[x][y] = 0\n",
    "#         return 0\n",
    "#     if ans[x][y] !=-1:\n",
    "#         return ans[x][y]\n",
    "#     else:\n",
    "#         if y <= x:\n",
    "#             ans[x][y] = 0\n",
    "#             return 0\n",
    "#         tempmin = y*y\n",
    "#         for i in range(x,y+1):\n",
    "#             tempmin = min(tempmin,i+max(search(x,i-1),search(i+1,y)))\n",
    "#         ans[x][y] = tempmin\n",
    "#         return tempmin\n",
    "# search(1,n)\n",
    "# print(ans[1])\n",
    "ans=[-1,0,1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 21, 24, 27, 30, 34, 38, 42, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 86, 90, 94, 98, 102, 106, 110, 114, 119, 124, 129, 134, 139, 144, 149, 154, 160, 166, 172, 178, 182, 186, 190, 194, 198, 202, 206, 210, 214, 218, 222, 226, 230, 234, 238, 242, 246, 250, 254, 258, 262, 266, 270, 274, 278, 282, 286, 290, 295, 300, 305, 310, 315, 320, 325, 330, 335, 340, 345, 350, 355, 360, 365, 370, 376, 382, 388, 394, 400, 406, 412, 418, 424, 430, 436, 442, 448, 454, 460, 466, 473, 480, 487, 494, 501, 508, 515, 522, 529, 536, 543, 550, 555, 560, 565, 570, 575, 580, 585, 590, 595, 600, 605, 610, 615, 620, 625, 630, 635, 640, 645, 650, 655, 660, 666, 674, 680, 686, 692, 698, 703, 708, 713, 718, 723, 728, 733, 738, 743, 748, 753, 758, 763, 768, 773, 778, 783, 788, 793, 798, 803, 808, 813, 818, 823, 828, 833, 838, 843, 848, 853, 858, 863, 868, 873, 878, 883, 888, 893, 898, 904, 910, 916, 922, 928, 934, 940, 946, 952]\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        return ans[n]\n",
    "        #return ans[1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i >= j:\n",
    "        #         return 0\n",
    "        #     res = inf\n",
    "        #     for k in range(i, j + 1):\n",
    "        #         res = min(res, max(dfs(i,k-1), dfs(k+1,j)) + k)\n",
    "        #     return res\n",
    "        # return dfs(1, n)\n",
    "        f = [[0] * (n + 1) for i in range(n + 1)]\n",
    "        for i in range(n-1, 0, -1):\n",
    "            for j in range(i + 1, n + 1):\n",
    "                res = inf\n",
    "                for k in range(i, j):\n",
    "                    res = min(res, max(f[i][k-1], f[k+1][j]) + k)\n",
    "                f[i][j] = res\n",
    "        return f[1][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "f = [[0 for _ in range(201)] for _ in range(201)]\n",
    "for j in range(1, 201):\n",
    "    x = j - 1\n",
    "    q = deque()\n",
    "    for i in range(j - 1, 0, -1):\n",
    "        while f[i][x - 1] > f[x + 1][j]:\n",
    "            if q[0][0] >= x:\n",
    "                q.popleft()\n",
    "            x -= 1\n",
    "        while q and q[-1][1] >= f[i + 1][j] + i:\n",
    "            q.pop()\n",
    "        q.append((i, f[i + 1][j] + i))\n",
    "        f[i][j] = min(q[0][-1], f[i][x] + x + 1)\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        return f[1][n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        # dp[i][j] denotes the minimum cost for interval [i, j] to gurantee the victory \n",
    "\n",
    "        for i in range(n, 0, -1):\n",
    "            for j in range(i+1, n+1):\n",
    "                dp[i][j] = j + dp[i][j-1]\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], k + max(dp[i][k-1], dp[k+1][j]))\n",
    "\n",
    "        return dp[1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[float('inf')]*n for _ in range(n)]\n",
    "\n",
    "        for i in range(n)[::-1]:\n",
    "            for j in range(i, n):\n",
    "                if i != j:\n",
    "                    for k in range(i, j+1):\n",
    "                        if k == i:\n",
    "                            dp[i][j] = min(dp[i][j], dp[k+1][j]+k+1)\n",
    "                        elif k == j:\n",
    "                            dp[i][j] = min(dp[i][j], dp[i][k-1]+k+1)\n",
    "                        else:\n",
    "                            dp[i][j] = min(dp[i][j], max(dp[i][k-1], dp[k+1][j])+k+1)\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "        # for d in dp:\n",
    "        #     print(d)\n",
    "\n",
    "        return dp[0][n-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        if n == 1: return 0\n",
    "        dp = [[float('inf')] * (n + 1) for _ in range(n + 1)]\n",
    "        for i in range(0, n + 1):\n",
    "            dp[i][i] = 0 \n",
    "        for i in range(2, n + 1):\n",
    "            for j in range(i - 1, 0, -1):\n",
    "                if j == i - 1: dp[j][i] = j \n",
    "                else:\n",
    "                    for k in range(j + 1, i):\n",
    "                        dp[j][i] = min(dp[j][i], k + max(dp[j][k-1] , dp[k+1][i]))\n",
    "        return dp[1][n]            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[0 for i in range(n + 1)] for j in range(n + 1)]\n",
    "        for j in range(1, n + 1):\n",
    "            for i in range(j - 1, 0, -1):\n",
    "                dp[i][j] = n*n\n",
    "                if i == j:\n",
    "                    dp[i][j] = 0\n",
    "                elif j - i <= 2:\n",
    "                    dp[i][j] = j - 1\n",
    "                else:\n",
    "                    for k in range(i, j):\n",
    "                        dp[i][j] = min(dp[i][j], max(dp[i][k - 1], dp[k + 1][j]) + k )\n",
    "        #print(dp)\n",
    "        return dp[1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[0] * (n+1) for _ in range(n+1)]\n",
    "        for i in range(n, 0, -1):\n",
    "            for j in range(i+1, n+1):\n",
    "                dp[i][j] = float('inf')\n",
    "                for k in range(i,j):\n",
    "                    dp[i][j] = min(dp[i][j], max(dp[i][k-1] +k, dp[k+1][j] + k))\n",
    "        print(dp)\n",
    "        return dp[1][n]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[0] * (n+1) for i in range(n+1)]\n",
    "\n",
    "        for i in range(n, -1, -1):\n",
    "            for j in range(i+1, n+1):\n",
    "                dp[i][j] = inf\n",
    "                for k in range(i, j):\n",
    "                    dp[i][j] = min(dp[i][j], k + max(dp[i][k-1], dp[k+1][j]))\n",
    "\n",
    "        print(dp)\n",
    "        return dp[1][n]\n",
    "        # @cache\n",
    "        # def dfs(i, j):\n",
    "        #     if i >= j:\n",
    "        #         return 0\n",
    "\n",
    "        #     res = inf\n",
    "\n",
    "        #     for k in range(i, j+1):\n",
    "        #         res = min(res, max(dfs(i,k-1), dfs(k+1, j)) + k)\n",
    "        #     return res\n",
    "        \n",
    "        # return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[((1 + n) * n // 2) for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        # dp[i][j] stands guess from i to j, you need at least $dp[i][j]\n",
    "        # dp[x][x] = 0\n",
    "        for i in range(1, n + 1):\n",
    "            dp[i][i] = 0\n",
    "        for step in range(1, n + 1):\n",
    "            for i in range(1, n - step + 1):\n",
    "                j = i + step\n",
    "                for k in range(i, j + 1):\n",
    "                    leftnum = 0 if k == i else dp[i][k - 1]\n",
    "                    rightnum = 0 if k == j else dp[k + 1][j]\n",
    "                    dp[i][j] = min(dp[i][j], k + max(leftnum, rightnum))\n",
    "        return dp[1][n] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # f[i][i] = 0 f[i][i + 1] = i\n",
    "        f = [[0 for _ in range(n + 1)] for _ in range(n + 1)]\n",
    "        for j in range(1, n + 1):\n",
    "            x = j - 1\n",
    "            for i in range(j - 1, 0, -1):\n",
    "                f1 = max(f[i][x-1], f[x+1][j]) + x\n",
    "                print(x - 1, x + 1)\n",
    "                while x - 1 >= i and max(f[i][x-2], f[x][j]) + x - 1 <= f1:\n",
    "                    f1 = max(f[i][x-2], f[x][j]) + x - 1\n",
    "                    x -= 1\n",
    "                f[i][j] = f1\n",
    "                # print(i, x, j)\n",
    "        print(f)\n",
    "        return f[1][n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        self.memo = {}\n",
    "        return self.dp(1,n)\n",
    "\n",
    "    def dp(self,left,right):\n",
    "        key = (left,right)\n",
    "        if(key in self.memo):\n",
    "            return self.memo[key]\n",
    "        '''均为闭区间'''\n",
    "        if(left==right):\n",
    "            return 0\n",
    "        if(left+1==right):\n",
    "            return left\n",
    "        res = float('inf')\n",
    "        for i in range(left,right+1):\n",
    "            tmp = i+max(self.dp(left,i-1),self.dp(i+1,right))\n",
    "            if(tmp<res):\n",
    "                res = tmp\n",
    "        self.memo[key] = res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        sums = list(itertools.accumulate(range(n + 1)))\n",
    "        mem = [[-1 for i in range(n + 1)] for j in range(n + 1)]\n",
    "        # @cache\n",
    "        def DFS(l, r, cost):\n",
    "            if l >= r:\n",
    "                return cost\n",
    "            if l == r - 1:\n",
    "                return l + cost\n",
    "            if mem[l][r] > -1:\n",
    "                return mem[l][r] + cost\n",
    "            ret = 0x7fffffff\n",
    "            for mid in range(l + 1, r):\n",
    "                ret = min(ret, max(DFS(l, mid - 1, cost + mid), DFS(mid + 1, r, cost + mid)))\n",
    "            mem[l][r] = ret - cost\n",
    "            return ret\n",
    "        return DFS(1, n, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        mem = [[0] * (n+1) for _ in range(n+1)]\n",
    "\n",
    "        def cost(low, high):\n",
    "            if low >= high:\n",
    "                return 0\n",
    "            if mem[low][high] != 0:\n",
    "                return mem[low][high]\n",
    "            res = float('inf')\n",
    "            for i in range((low+high)//2, high + 1):\n",
    "                tmp = i + max(cost(low, i-1), cost(i+1, high)) # 遭遇最坏情况\n",
    "                res = min(res, tmp) # 花费最少\n",
    "            mem[low][high] = res\n",
    "            return res\n",
    "        \n",
    "        return cost(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        mem = [[0]*(n+1) for _ in range(n+1)]\n",
    "        print(mem)\n",
    "        def cal(a,b):\n",
    "            if a>=b:\n",
    "                return 0\n",
    "            if mem[a][b]!=0:\n",
    "                return mem[a][b]\n",
    "            res = 100000\n",
    "            for i in range(a,b):\n",
    "                res = min(res,i+max(cal(a,i-1),cal(i+1,b)))\n",
    "               # print(res)\n",
    "            mem[a][b] = res\n",
    "            return res\n",
    "        return cal(1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def cost(left, right):\n",
    "    if left >= right:\n",
    "        return 0\n",
    "    ans = inf\n",
    "    for mid in range(left, right + 1):\n",
    "        ans = min(ans, mid + max(cost(left, mid - 1), cost(mid + 1, right)))\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        return cost(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        vis=[[0]*(n+3) for i in range(n+3)]\n",
    "        f=[[40000]*(n+3) for i in range(n+3)]\n",
    "        def dfs(u,v):\n",
    "            nonlocal vis,f\n",
    "            if(vis[u][v]):return f[u][v]\n",
    "            vis[u][v]=1\n",
    "            if(u>=v):f[u][v]=0;return 0\n",
    "            for i in range(u+(v-u)//2,v+1):\n",
    "                f[u][v]=min(f[u][v],i+max(dfs(u,i-1),dfs(i+1,v)))\n",
    "            return f[u][v]\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        from functools import lru_cache\n",
    "        # 如果只有一个数，直接返回0\n",
    "        # 如果只有两个数，返回其中小的\n",
    "        # 如果只有三个数，直接返回中间这个数\n",
    "        # 如果有更多的数字呢？\n",
    "        # 假设有个mid\n",
    "        # 那么x=[left,mid]单调增加：随着mid的增加而增加\n",
    "        # 而y=[mid,right]单调减少，随着mid的增加而减少\n",
    "        # 找到一个mid，使得min(max(x,y))取得极大极小值\n",
    "\n",
    "        @lru_cache(None,False)\n",
    "        def myMoney(left: int, right: int) -> int:\n",
    "            if left>=right:\n",
    "                return 0\n",
    "            # if right-left==1:\n",
    "            #     return left \n",
    "            # if right-left==2:\n",
    "            #     return left+1\n",
    "            mid = (left+right)//2\n",
    "            tt = []\n",
    "            xx, yy = {}, {}\n",
    "            x, y = 0, 1\n",
    "            while x<y:\n",
    "                x = myMoney(left,mid-1)\n",
    "                y = myMoney(mid+1,right)\n",
    "                tt.append(mid)\n",
    "                xx[mid] = x \n",
    "                yy[mid] = y\n",
    "                mid += 1\n",
    "            return min([max([xx[z]+z,z+yy[z]]) for z in tt])\n",
    "\n",
    "        return myMoney(1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        def helper(i, j, memo):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            res = float('inf')\n",
    "            for k in range(i, j+1):\n",
    "                cur = max(helper(i, k-1, memo), helper(k+1, j, memo)) + k\n",
    "                res = min(res, cur)\n",
    "            memo[(i, j)] = res\n",
    "            return memo[(i, j)]\n",
    "        return helper(1, n, {})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        cache=[[-1]*(n+1) for _ in range(n+1)]\n",
    "        def dfs(l,r):\n",
    "            if l>=r:\n",
    "                return 0 \n",
    "            if cache[l][r]!=-1:\n",
    "                return cache[l][r]\n",
    "            ans=0\n",
    "            res=inf\n",
    "            for x in range(l,r+1):\n",
    "                ans=max(dfs(l,x-1),dfs(x+1,r))+x\n",
    "                res=min(res,ans)\n",
    "            cache[l][r]=res\n",
    "            return res\n",
    "        return dfs(1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[-1]*(n+2) for i in range(n+2)]\n",
    "        for i in range(n+2):\n",
    "            dp[i][i] = 0\n",
    "            if i != n+1:\n",
    "                dp[i][i+1] = 0\n",
    "        def dfs(l,r):\n",
    "            if dp[l][r] != -1:\n",
    "                return dp[l][r]\n",
    "            result = inf\n",
    "            for i in range(l,r):\n",
    "                result = min(result,max(dfs(l,i),dfs(i+1,r))+i)\n",
    "            dp[l][r] = result\n",
    "            print(l,r,result)\n",
    "            return result\n",
    "        return dfs(1,n+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        f=[[0]*201 for _ in range(201)]\n",
    "        def dfs(l,r):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            if f[l][r]!=0:\n",
    "                return f[l][r]\n",
    "            res=float('inf')\n",
    "            for i in range(l,r+1):\n",
    "                cur=max(dfs(l,i-1),dfs(i+1,r))+i\n",
    "                res=min(res,cur)\n",
    "            f[l][r]=res\n",
    "            return res\n",
    "        return dfs(1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(1, n):\n",
    "            dp[i][i+1] = i\n",
    "        def f_getDpElem(i, j):\n",
    "            # print(\"i = {}, j = {}\".format(i, j))\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if dp[i][j] != 0:\n",
    "                return dp[i][j]\n",
    "            a = min([k+max(f_getDpElem(i, k-1), f_getDpElem(k+1, j)) for k in range(i, j+1)])\n",
    "            dp[i][j] = a\n",
    "            return dp[i][j]\n",
    "        return f_getDpElem(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        dp = [[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(1, n):\n",
    "            dp[i][i+1] = i\n",
    "        def f_getDpElem(i, j):\n",
    "            # print(\"i = {}, j = {}\".format(i, j))\n",
    "            if dp[i][j] != 0:\n",
    "                return dp[i][j]\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            a = min([k+max(f_getDpElem(i, k-1), f_getDpElem(k+1, j)) for k in range(i, j)])\n",
    "            dp[i][j] = a\n",
    "            return dp[i][j]\n",
    "        return f_getDpElem(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        def dfs(l,r):\n",
    "            if( r - l < 1): return 0\n",
    "            if (cache[l][r] != 0):  return cache[l][r]      \n",
    "\n",
    "            ans = inf\n",
    "            for x in range(l, r + 1):\n",
    "                lCount = dfs(l, x - 1) if cache[l][x - 1] == 0 else cache[l][x - 1]\n",
    "                rCount = dfs(x + 1, r) if cache[x + 1][r] == 0 else cache[x + 1][r]\n",
    "\n",
    "                cur = max(lCount, rCount) + x\n",
    "                ans = min(ans, cur)\n",
    "\n",
    "            cache[l][r] = ans;\n",
    "            return ans;\n",
    "        cache = [[0] * 210 for _ in range(210)]\n",
    "        return dfs(1, n)\n",
    "\n",
    "   \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        vis=[[0]*(n+3) for i in range(n+3)]\n",
    "        f=[[40000]*(n+3) for i in range(n+3)]\n",
    "        def dfs(u,v):\n",
    "            nonlocal vis,f\n",
    "            if(vis[u][v]):return f[u][v]\n",
    "            vis[u][v]=1\n",
    "            if(u>=v):f[u][v]=0;return 0\n",
    "            for i in range(u,v+1):\n",
    "                f[u][v]=min(f[u][v],i+max(dfs(u,i-1),dfs(i+1,v)))\n",
    "            return f[u][v]\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        f = [[0] * 201 for _ in range(201)]\n",
    "\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            \n",
    "            if f[l][r]:\n",
    "                return f[l][r]\n",
    "\n",
    "            ans = float('inf') \n",
    "            for i in range(l, r+1):\n",
    "                lmax = dfs(l,i-1)\n",
    "                rmax = dfs(i+1,r)\n",
    "                max_ = max(lmax, rmax)\n",
    "                if ans > max_ + i:\n",
    "                    ans = max_ + i \n",
    "\n",
    "            f[l][r] = ans\n",
    "\n",
    "            return ans \n",
    "        \n",
    "        return dfs(1, n)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        mem = collections.defaultdict(collections.defaultdict)\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "            \n",
    "            if l in mem and r in mem[l]:\n",
    "                return mem[l][r]\n",
    "            \n",
    "            res = float('inf')\n",
    "            for i in range(l, r+1):\n",
    "                res = min(res, i + max(dfs(l, i-1), dfs(i+1, r)))\n",
    "            \n",
    "            mem[l][r] = res\n",
    "            return res\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # global save\n",
    "        save = dict()\n",
    "        def dfs(l,r):\n",
    "            # global save\n",
    "            if save.get(l,-1)!=-1 and save[l].get(r,-1)!=-1:\n",
    "                return save[l][r]\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            res = 0\n",
    "            # mid = l+((r-l)>>1)\n",
    "            # res = mid+max(dfs(l,mid-1),dfs(mid+1,r))\n",
    "            for ii in range(l,r+1):\n",
    "                ans = ii+max(dfs(l,ii-1),dfs(ii+1,r))\n",
    "                if res==0:\n",
    "                    res = ans\n",
    "                else:\n",
    "                    res = min(res,ans)\n",
    "               \n",
    "            if save.get(l,-1)==-1:\n",
    "                save[l] = dict()\n",
    "            save[l][r] = res\n",
    "            return res\n",
    "        return dfs(1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        mem = {}\n",
    "        def dp(start, end):\n",
    "            if end-start < 1:\n",
    "                return 0\n",
    "            if (start, end) in mem:\n",
    "                return mem[(start, end)]\n",
    "            res = float('inf')\n",
    "            mid = (start+end)//2\n",
    "            for i in range(mid, end):\n",
    "                res = min(res, i+max(dp(start, i-1), dp(i+1, end)))\n",
    "            mem[(start, end)] = res\n",
    "            return res\n",
    "\n",
    "        return dp(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:   \n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        cache1=[[0 for i in range(206)] for j in range(206)]\n",
    "        def dfs(l,r):\n",
    "            if l>=r:\n",
    "                return 0\n",
    "            if cache1[l][r]:\n",
    "                return cache1[l][r]\n",
    "            ans=0x3f3f3f3f3f\n",
    "            for k in range(l,r+1):\n",
    "                win=max(dfs(l,k-1),dfs(k+1,r))+k\n",
    "                ans=min(ans,win)\n",
    "            cache1[l][r]=ans\n",
    "            return ans\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        adict = {}\n",
    "        def divide(start, end):\n",
    "            if (start, end) in adict:\n",
    "                return adict[(start, end)]\n",
    "            if end <= start:\n",
    "                return 0\n",
    "            if end - start == 1:\n",
    "                return start\n",
    "            mid = (start + end) // 2\n",
    "            ans = min([i + max(divide(start, i - 1), divide(i + 1, end)) for i in range(mid, end)])\n",
    "            adict[(start, end)] = ans\n",
    "            return ans\n",
    "        return divide(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        mem = [[0] * n for _ in range(n)]\n",
    "        def getmoneyrange(start, end):\n",
    "            if start >= end:\n",
    "                return 0\n",
    "            if mem[start -1][end - 1] != 0:\n",
    "                return mem[start -1][end -1]\n",
    "            res = min([max(getmoneyrange(start, k-1), getmoneyrange(k+1, end)) + k for k in range(start, end)])\n",
    "            mem[start - 1][end - 1] = res\n",
    "            return res\n",
    "        return getmoneyrange(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        t = ((0, 0), (1, 0), (1, 1), (2, 2), (2, 4), (2, 6), (2, 8))\n",
    "        \n",
    "        @cache\n",
    "        def f(a, b):\n",
    "            if (c := b - a) < 7:\n",
    "                i, j = t[c]\n",
    "                return a * i + j\n",
    "            return min(i + max(f(a, i - 1), f(i + 1, b)) for i in range((a + b - 1) >> 1, b))\n",
    "        \n",
    "        return f(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(a, b):\n",
    "            if a >= b:\n",
    "                return 0\n",
    "            else:\n",
    "                return min(i+max(dfs(a, i-1), dfs(i+1, b)) for i in range((a+b)>>1, b+1))\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j):  # 区间 [i, j] 上，需要最小现金\n",
    "            if i == j:\n",
    "                return 0\n",
    "            if i + 1 == j:\n",
    "                return i\n",
    "            res = inf\n",
    "            for k in range((i + j) // 2, j):\n",
    "                res = min(res, max(dfs(i, k - 1), dfs(k + 1, j)) + k)\n",
    "            return res\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            return min(max(dfs(i, x - 1), dfs(x + 1, j)) + x  for x in range((i + j) // 2, j + 1))\n",
    "        return dfs(1, n)\n",
    "\n",
    "# class Solution:\n",
    "#     def getMoneyAmount(self, n: int) -> int:\n",
    "#         @cache \n",
    "#         def f(i,j):\n",
    "#             if j - i <= 1 : return 0 \n",
    "#             return min(\n",
    "#                 [k+max(f(i,k),f(k+1,j)) for k in range(i+j-1>>1,j)]\n",
    "#             )\n",
    "#         return f(1,n+1)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(left:int,right:int)->int:\n",
    "            if left == right:\n",
    "                return 0\n",
    "            if right - left == 1:\n",
    "                return left\n",
    "            result = []\n",
    "            for i in range(left+int((right-left)*0.4),right-int((right-left)*0.1)+1):\n",
    "                result.append(i+max(dfs(left,i-1),dfs(i+1,right)))\n",
    "            return min(result,default=0)\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # 返回[a..b]的ans\n",
    "        @lru_cache(None)\n",
    "        def f(a, b):\n",
    "            if a >= b:\n",
    "                return 0\n",
    "            if a + 1 == b:\n",
    "                return a\n",
    "            if a + 2 == b:\n",
    "                return a + 1\n",
    "            \n",
    "            m = (a + b) // 2\n",
    "            res = m + max(f(a, m-1), f(m+1, b))\n",
    "            \n",
    "            # i = [m+1, ..., b]\n",
    "            for i in range(m+1, b+1):\n",
    "                # l单调增，r单调减\n",
    "                l = f(a, i-1)\n",
    "                r = f(i+1, b)\n",
    "                res = min(res, i + max(l, r))\n",
    "                if l >= res:\n",
    "                    break\n",
    "                \n",
    "            # i = [m-1, m-2 ..., a]\n",
    "            for i in range(m-1, a-1, -1):\n",
    "                # l单调增，r单调减\n",
    "                l = f(a, i-1)\n",
    "                r = f(i+1, b)\n",
    "                res = min(res, i + max(l, r))\n",
    "                if r >= res:\n",
    "                    break\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return f(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # dp=[0]*(n+1)\n",
    "        @functools.lru_cache(None)\n",
    "        # vis=[[float('inf')]*(n+1) for i in range(n+1)]\n",
    "        # for i in range(1,n+1):\n",
    "        #     vis[i][i]=0\n",
    "        #     vis[i-1][i]=i-1\n",
    "        ##下面已经是简单优化版本，未优化看提交记录\n",
    "        def dp(m,n):\n",
    "            if m==n:\n",
    "                return 0\n",
    "            if n==m+1:\n",
    "                return m\n",
    "            # if vis[m][n]!=float('inf'):\n",
    "            #     return vis[m][n]\n",
    "            res=(m+n)*(n-m)//2+2\n",
    "            for x in range(m+1,n):\n",
    "                if x<=(m+n)>>1:\n",
    "                    t=dp(x+1,n)+x\n",
    "                else:\n",
    "                    t=dp(m,x-1)+x if dp(m,x-1)>dp(x+1,n) else dp(x+1,n)+x\n",
    "                res=res if res<=t else t\n",
    "                # vis[m][n]=res\n",
    "            return res\n",
    "        return dp(1,n)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        if n <= 3:\n",
    "            return [0, 0, 1, 2, 4][n]\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if j - i == 1:\n",
    "                return i\n",
    "            return min(max(dfs(i, x - 1), dfs(x + 1, j)) + x for x in range(j - 1, (i + j) // 2 - 1, -1))\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(left,right):\n",
    "            if left==right:\n",
    "                return 0\n",
    "            if left==right-1:\n",
    "                return left\n",
    "            max_money=0\n",
    "            min_max_money=0x7fffffff\n",
    "            for i in range(left+(right-left)//2,right):\n",
    "                rmoney=dfs(i+1,right)+i\n",
    "                lmoney=dfs(left,i-1)+i\n",
    "                max_money=max(rmoney,lmoney)\n",
    "                min_max_money=min(min_max_money,max_money)\n",
    "            return min_max_money\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        mem={}\n",
    "        def dfs(l,r):\n",
    "            if l==r:\n",
    "                return 0\n",
    "            if r-l==1:\n",
    "                return l\n",
    "            if (l,r) in mem:\n",
    "                return mem[(l,r)]\n",
    "            ans=float('inf')\n",
    "            for i in range(l,r+1):\n",
    "                ans=min(ans,i+max(dfs(l,i-1),dfs(i+1,r)))\n",
    "            mem[(l,r)]=ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        mem={}\n",
    "        def dfs(l,r):\n",
    "            if l==r:\n",
    "                return 0\n",
    "            if r-l==1:\n",
    "                return l\n",
    "            if (l,r) in mem:\n",
    "                return mem[(l,r)]\n",
    "            ans=float('inf')\n",
    "            for i in range(l,r+1):\n",
    "                ans=min(ans,i+max(dfs(l,i-1),dfs(i+1,r)))\n",
    "            mem[(l,r)]=ans\n",
    "            return ans\n",
    "\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dp(L, R):\n",
    "            if L >= R:\n",
    "                return 0\n",
    "            ans = float(\"inf\")\n",
    "            Left = int(L + (R - L) * 0.3)\n",
    "            Right = max(R, int(L + (R - L) * 0.7))\n",
    "            for mid in range(Left, Right + 1):\n",
    "                ans = min(ans, mid + max(dp(L, mid - 1), dp(mid + 1, R)))\n",
    "            return ans\n",
    "\n",
    "        return dp(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(left:int,right:int)->int:\n",
    "            if left == right:\n",
    "                return 0\n",
    "            if right - left == 1:\n",
    "                return left\n",
    "            result = []\n",
    "            for i in range(left+int((right-left)*0.3),right+1):\n",
    "                result.append(i+max(dfs(left,i-1),dfs(i+1,right)))\n",
    "            return min(result,default=0)\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        def cal(i, j):\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            if j - i == 1:\n",
    "                return i\n",
    "            ma = n ** 2\n",
    "            for k in range(i+1, j):\n",
    "                cur = k + max(cal(i, k-1), cal(k+1, j))\n",
    "                if cur < ma:\n",
    "                    ma = cur\n",
    "            memo[(i, j)] = ma\n",
    "            return ma\n",
    "        memo = dict()\n",
    "        return cal(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        cache = dict()\n",
    "        def dfs(left, right):\n",
    "            if left == right:\n",
    "                return 0\n",
    "            if right - left == 1:\n",
    "                return left\n",
    "            if (left, right) in cache:\n",
    "                return cache[(left, right)]\n",
    "            cur_min = float(\"inf\")\n",
    "            for m in range(left+1, right):\n",
    "                tmp_min = max(dfs(left, m-1), dfs(m+1, right)) + m\n",
    "                if tmp_min < cur_min:\n",
    "                    cur_min = tmp_min\n",
    "            cache[(left, right)] = cur_min\n",
    "            return cache[(left, right)]\n",
    "        \n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        return self.dfs(1,n)\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def dfs(self, start, end):\n",
    "        if end == start:\n",
    "            return 0\n",
    "        if end == start + 1:\n",
    "            return start\n",
    "        result = 10000\n",
    "        for i in range((start+end)//2, end):\n",
    "            result = min(result, i+max(self.dfs(start,i-1), self.dfs(i+1,end)))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i + 1 == j:\n",
    "                return i\n",
    "            if i == j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i + 1, j):\n",
    "                res = min(res, max(dfs(i, k - 1), dfs(k + 1, j)) + k)\n",
    "            return res\n",
    "        return dfs(0, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j:return 0\n",
    "            elif i+1 == j:return i\n",
    "            res = inf\n",
    "            for k in range(i+1, j):\n",
    "                res = min(res, max(dfs(i,k-1), dfs(k+1,j)) + k)\n",
    "            return res\n",
    "        return dfs(1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l == r :\n",
    "                return 0\n",
    "            if l == r - 1:\n",
    "                return l\n",
    "            res=200**2\n",
    "            for i in range(l+1 , r):\n",
    "                res=min(res,i+max(dfs(l,i-1),dfs(i+1,r)))\n",
    "            return res\n",
    "        ans=dfs(1,n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # f[i][j]表示[i, j]范围内确保能猜中获胜所需的最小现金\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i, j+1):\n",
    "                res = min(res, max(dfs(i, k-1), dfs(k+1, j)) + k)\n",
    "            return res\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            \n",
    "            ret = inf\n",
    "            for x in range(i, j+1):\n",
    "                ret = min(ret, max(dfs(i, x - 1) + x, dfs(x + 1, j) + x))\n",
    "            return ret\n",
    "        \n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        #dic = {}\n",
    "        @functools.lru_cache(maxsize = None)\n",
    "        def dp(l, r):\n",
    "            if l == r:\n",
    "                res = 0\n",
    "            elif l+1 == r:\n",
    "                res = l\n",
    "            elif l+2 == r:\n",
    "                res = l+1\n",
    "            else:\n",
    "                res = min(max(dp(l,x-1), dp(x+1,r))+x for x in range(l+1, r))\n",
    "            return res\n",
    "            \n",
    "        return dp(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i >= j: return 0\n",
    "\n",
    "            return min(max(dfs(i, k - 1), dfs(k + 1, j)) + k for k in range(i, j))\n",
    "            \n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            ans = min(max(dfs(i, k-1), dfs(k+1, j)) + k for k in range(i, j))\n",
    "            return ans\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        def DP(lo, hi):\n",
    "            if lo == hi: \n",
    "                return 0\n",
    "            elif lo + 1 == hi:\n",
    "                return lo\n",
    "            elif (lo, hi) in cache:\n",
    "                return cache[(lo, hi)]\n",
    "            else:\n",
    "                tmp = float('inf')\n",
    "                for mid in range(lo+1, hi):\n",
    "                    left = DP(lo, mid-1)\n",
    "                    right = DP(mid+1, hi)\n",
    "                    tmp = min(tmp, max(left, right) + mid)\n",
    "                cache[lo, hi] = tmp\n",
    "                return tmp\n",
    "                \n",
    "        cache = collections.defaultdict(int)\n",
    "        return DP(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        self.dp = dict()\n",
    "        def getMin(left, right):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            if left == right - 1:\n",
    "                return left\n",
    "            if (left, right) in self.dp:\n",
    "                return self.dp[(left, right)]\n",
    "            m = float('inf')\n",
    "            for i in range(left + 1, right):\n",
    "                m = min(i + max(getMin(left, i - 1), getMin(i + 1, right)), m)\n",
    "            self.dp[(left, right)] = m\n",
    "            return m\n",
    "        return getMin(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        map1={}\n",
    "        def dfs(x,y):\n",
    "            if (x,y) in map1:\n",
    "                return map1[(x,y)]\n",
    "            if y<=x:\n",
    "                return 0\n",
    "            if y-x==1:\n",
    "                return x\n",
    "            if y-x==2:\n",
    "                return x+1\n",
    "            ans=99999\n",
    "            for m in range(x,y+1):\n",
    "                t=max(dfs(x,m-1),dfs(m+1,y))+m\n",
    "                ans=min(ans,t)\n",
    "            map1[(x,y)]=ans\n",
    "            return ans\n",
    "        return (dfs(1,n)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        def DP(lo, hi):\n",
    "            if lo == hi: \n",
    "                return 0\n",
    "            elif lo + 1 == hi:\n",
    "                return lo\n",
    "            elif (lo, hi) in cache:\n",
    "                return cache[(lo, hi)]\n",
    "            else:\n",
    "                tmp = float('inf')\n",
    "                for mid in range(lo+1, hi):\n",
    "                    left = DP(lo, mid-1)\n",
    "                    right = DP(mid+1, hi)\n",
    "                    tmp = min(tmp, max(left, right) + mid)\n",
    "                cache[lo, hi] = tmp\n",
    "                return tmp\n",
    "                \n",
    "        cache = collections.defaultdict(int)\n",
    "        return DP(0, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # 区间dp\n",
    "        # dp[i][j] = k + max(dp[i][k-1], dp[k+1][j])\n",
    "        # 边界条件：如果i+1 == j, dp[i][j] = i\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i + 1 == j:\n",
    "                dp[i][j] = i\n",
    "                return dp[i][j]\n",
    "            if i == j:\n",
    "                dp[i][j] = 0\n",
    "                return dp[i][j]\n",
    "            if dp[i][j] == 10 ** 9:\n",
    "                for k in range(i + 1, j):\n",
    "                    dp[i][j] = min(dp[i][j], k + max(dfs(i,k-1), dfs(k+1,j)))\n",
    "            return dp[i][j]\n",
    "\n",
    "        dp = [[10 ** 9] * (1 + n) for _ in range(1 + n)]\n",
    "        return dfs(1, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @functools.lru_cache(maxsize=None)\n",
    "        def _getMoneyAmount(l,r):\n",
    "            if l >= r - 1:\n",
    "                return 0\n",
    "            if l == r - 2:\n",
    "                return l\n",
    "            res = []\n",
    "            for i in range(l, r):\n",
    "                res.append(i + max(_getMoneyAmount(l,i), _getMoneyAmount(i+1,r)) )\n",
    "            return min(res)\n",
    "        return _getMoneyAmount(1, n+1)\n",
    "\n",
    "        # @functools.lru_cache(maxsize=None)\n",
    "        # def sol(l, r) :\n",
    "        #     if r-l == 2 : return l\n",
    "        #     if r-l <= 1 : return 0\n",
    "        #     return min((i+max(sol(l,i), sol(i+1,r)) for i in range(l, r)))\n",
    "        # return sol(1,n+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def inner(start, end):\n",
    "            if end <= start:\n",
    "                return 0\n",
    "            result = None\n",
    "            for i in range(start, end + 1):\n",
    "                current = max(inner(start, i - 1), inner(i + 1, end)) + i\n",
    "                if result is None:\n",
    "                    result = current\n",
    "                else:\n",
    "                    result = min(result, current)\n",
    "            return result\n",
    "        \n",
    "        result = inner(1, n)\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # 递归\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i+1 == j:\n",
    "                return i\n",
    "            if i == j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i,j):\n",
    "                res = min(res,max(dfs(i,k-1),dfs(k+1,j))+k)\n",
    "            return res\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # 我猜了i,j之中的一个数k\n",
    "        # 代价为max(dfs(i,k-1),dfs(k+1,j))+k\n",
    "        # 边界,i==k return 0\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i >= j:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for k in range(i,j):\n",
    "                res = min(max(dfs(i,k-1),dfs(k+1,j))+k,res)\n",
    "            return res\n",
    "        return dfs(1,n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j):\n",
    "            return min([k+max(dfs(i,k),dfs(k+1,j)) for k in range(i,j)]) if j - i > 1 else 0\n",
    "        return dfs(1, n+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(low,high):\n",
    "            if low >= high:\n",
    "                return 0\n",
    "        \n",
    "            return min(max(dfs(low,k-1),dfs(k+1,high))+k for k in range(low,high+1))\n",
    "        return dfs(0,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "\n",
    "        def dfs(i,j):   #边界条件\n",
    "\n",
    "            if i+1==j:  #一共2个数肯定猜小的 对了错了都知道答案\n",
    "\n",
    "                return i\n",
    "\n",
    "            if i==j:    #只有1个数就不用猜了\n",
    "\n",
    "                return 0\n",
    "\n",
    "            res = 200**2 #最坏情况是(n+1)*n/2,所以选个足够大的数字\n",
    "\n",
    "            for k in range(i+1,j):\n",
    "\n",
    "                res=min(res,max(dfs(i,k-1),dfs(k+1,j))+k)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        # if n == 2:\n",
    "        #     return 1\n",
    "        # if n == 3:\n",
    "        #     return 2\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == j:\n",
    "                return 0\n",
    "            if (i+1) == j:\n",
    "                return i \n",
    "\n",
    "            minnum = 99999\n",
    "            # 1 4\n",
    "            # 2 3\n",
    "            for k in range(i+1, j):\n",
    "                maxnum = max(dfs(i, k-1), dfs(k+1, j)) + k\n",
    "                minnum = min(minnum, maxnum)\n",
    "            return minnum\n",
    "        return dfs(1, n)\n",
    "\n",
    "    # min 1-n (k + max(dfs(1, k), dfs(k, j)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(l: int, r: int) -> int:\n",
    "            if l == r:\n",
    "                return 0\n",
    "            if l + 1 == r:\n",
    "                return l\n",
    "            ans = inf\n",
    "            for i in range(l + 1, r):\n",
    "                cur = max(f(l, i - 1), f(i + 1, r)) + i\n",
    "                ans = min(cur, ans)\n",
    "            return ans\n",
    "        return f(1, n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        #copy\n",
    "        @cache\n",
    "        def dfs(l,r):\n",
    "            if l == r:\n",
    "                return 0\n",
    "            if l ==r-1:\n",
    "                return l\n",
    "            return min(i+max(dfs(l,i-1),dfs(i+1,r)) for i in range(l+1,r))\n",
    "        return dfs(1,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        memo = {}\n",
    "        def cost(i, j):\n",
    "            # denote the minimum money to make sure the victory when the currect interval is [i, j]\n",
    "            if (i, j) in memo:\n",
    "                return memo[(i, j)]\n",
    "            elif i>=j:\n",
    "                memo[(i, j)] = 0 \n",
    "                return 0 \n",
    "            else:\n",
    "                c = float('inf')\n",
    "                for guess in range(i, j+1):\n",
    "                    c = min( c, guess + max(cost(i, guess-1), cost(guess+1, j)) )\n",
    "                memo[(i, j)] = c \n",
    "                return c\n",
    "            \n",
    "        return cost(1, n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def getMoneyAmount(self, n: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def cost(i, j):\n",
    "            # denote the minimum money to make sure the victory when the currect interval is [i, j]\n",
    "            if i>=j:\n",
    "                return 0 \n",
    "            else:\n",
    "                c = float('inf')\n",
    "                for guess in range(i, j+1):\n",
    "                    c = min( c, guess + max(cost(i, guess-1), cost(guess+1, j)) )\n",
    "                return c\n",
    "            \n",
    "        return cost(1, n)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
